package dynamtic;

/**
 * @Auther Jun jie Yi
 * @Date 21:36 2022/2/25
 */
public class MinDistance {
    public static void main(String[] args) {
        System.out.println(minDistance("rad", "apple"));
    }

    //暴力递归解法，不使用记录
    public static int minDistance(String str1, String str2) {
        return dp(str1, str2, str1.length() - 1, str2.length() - 1);
    }

    static int dp(String str1, String str2, int i, int j) {
        //base case
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;
        if (str1.charAt(i) == str2.charAt(j)) {
            return dp(str1, str2, i - 1, j - 1);
        } else {
            return Math.min(Math.min(
                    dp(str1, str2, i, j - 1) + 1, //插入
                    dp(str1, str2, i - 1, j) + 1 //删除
                    ),
                    dp(str1, str2, i - 1, j - 1) + 1 //替换
            );
        }
    }


    public static int minDistance1(String word1, String word2) {
        int w1length = word1.length();
        int w2length = word2.length();
        int[][] dp = new int[w1length + 1][w2length + 1];
        for (int l = 0; l <= w2length; l++) {
            dp[0][l] = l;
        }
        for (int l = 0; l <= w1length; l++) {
            dp[l][0] = l;
        }
        for (int i = 1; i <= w1length; i++) {
            for (int j = 1; j <= w2length; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[w1length][w2length];
    }

}
